/*****************************************************
Copyright (C) 2019. All rights reserved.
File name     ：LinkedStack.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2019-12-28
Function List ：
Description   ：Linked Stack
******************************************************/

#include "LinkedStack.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"

/* Stack implementation is a linked list with a header */
struct Node {
    StackElementType Element;
    PtrToNode        Next;
};

int IsEmptyStack(LinkedStack S) {
    return S->Next == NULL;
}

LinkedStack CreateStack(void) {
    LinkedStack S;

    S = (LinkedStack)malloc(sizeof(struct Node));
    if (S == NULL) {
        FatalError("Out of space!!!");
    }

    S->Next = NULL;
    MakeEmptyStack(S);

    return S;
}

void DisposeStack(LinkedStack S) {
    MakeEmptyStack(S);
    free(S);
}

void MakeEmptyStack(LinkedStack S) {
    if (S == NULL) {
        Error("Must use CreateStack first");
    } else {
        while (!IsEmptyStack(S)) {
            Pop(S);
        }
    }
}

void Push(StackElementType X, LinkedStack S) {
    PtrToNode TmpCell;

    TmpCell = (PtrToNode)malloc(sizeof(struct Node));
    if (TmpCell == NULL) {
        FatalError("Out of space!!!");
    } else {
        TmpCell->Element = X;
        TmpCell->Next = S->Next;
        S->Next = TmpCell;
    }
}

StackElementType Top(LinkedStack S) {
    if (!IsEmptyStack(S)) {
        return S->Next->Element;
    } else {
        Error("Empty stack");
        return 0;  /* Return value used to avoid warning */
    }
}

void Pop(LinkedStack S) {
    PtrToNode FirstCell;

    if (IsEmptyStack(S)) {
        Error("Empty stack");
    } else {
        FirstCell = S->Next;
        S->Next = S->Next->Next;
        free(FirstCell);
    }
}

StackElementType TopAndPop(LinkedStack S) {
    PtrToNode FirstCell;
    StackElementType X = 0;

    if (IsEmptyStack(S)) {
        Error("Empty stack");
        return 0;  /* Return value used to avoid warning */
    } else {
        X = S->Next->Element;  /* Save the value of the first element */

        FirstCell = S->Next;
        S->Next = S->Next->Next;
        free(FirstCell);

        return X;
    }
}

// EOF

